import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    /**
     * 利用优先级队列做优化
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        // 1、创建一个小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);

        // 2、把所有的头结点放进小根堆
        for(ListNode list : lists) {
            if(list != null) {
                heap.offer(list);
            }
        }

        // 3、合并链表
        ListNode ret = new ListNode(0);
        ListNode prev = ret;

        while(!heap.isEmpty()) {
            ListNode t = heap.poll();
            prev.next = t;
            prev = t;
            if(t.next != null) heap.offer(t.next);
        }

        return ret.next;
    }

    /**
     * 暴力
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        if(lists.length == 0) return null;
        ListNode ret = lists[0];
        for(int i = 1; i < lists.length; i++) {
            ret = mergeTwoLists(ret, lists[i]);
        }

        return ret;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ret = new ListNode();
        ListNode cur = ret;
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
                cur = cur.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }

        if(list1 != null) {
            cur.next = list1;
        }
        if(list2 != null) {
            cur.next = list2;
        }

        return ret.next;
    }
}